package com.vans.practice.alghr;

import java.util.Arrays;

/**
 * @Description: 基数排序
 * @Note: 稳定， k为桶的数量
 * @平均时间复杂度： n * k
 * @空间复杂度： n + k
 * @Author elle
 * @Date 2020/10/14 11:55
 */
public class Radix {
    public static void main(String[] args) {
        int[] a = {9, 6, 19, 11, 1, 5, 10, 18};
//    int[] a = {9, 6, 19};
        int maxDigit = getMaxDigit(a);
        int[] r = sort(a, 0, maxDigit);
        System.out.println(Arrays.toString(r));
    }

    private static int[] sort(int[] a, int digit, int maxDigit) {
        if (digit > maxDigit) return a;
        //数组的长度
        int arrLen = a.length;
        //辅助数组, 用来存放按当前位排序好的数
        int[] help = new int[arrLen];
        //计数数组, 用来存放当前位数字出现的次数, 基数设置为10
        int[] count = new int[10];

        //循环数组, 按位统计数组中数字出现次数
        for (int i = 0; i < a.length; i++) {
            count[getValByDigit(a[i], digit)]++;
        }

        //将计数数组的值变成下标值
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i-1];
        }

        for (int i = a.length-1; i >= 0; i--) {
            int val = getValByDigit(a[i], digit);
            help[count[val]-1] = a[i];
            count[val]--;
        }
        return sort(help, digit+1, maxDigit);
    }

    /**
     * 获取数组中数的最大位数
     * @param a
     */
    private static int getMaxDigit(int[] a) {
        int max = 1;
        for (int i = 0; i < a.length; i++) {
            max = Math.max(String.valueOf(a[i]).length(),max);
        }
        return max;
    }

    /**
     * 获取一个数的第digit位上的数
     * @param num 数字
     * @param digit 位数(从0计算, 低位~高位)
     */
    private static int getValByDigit(int num, int digit) {
        //暂时写这么多
        int a[] = {1,10,100,1000,10000};
        return (num/a[digit] % 10);
    }

}
